"""
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的 回文 子串。
 
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
"""

# 中心扩展法
def longest_palindrome(s: str) -> str:
    """
    :type s: str
    :rtype: str
    """
    if not s: return ""

    max_len = 1
    start = 0

    for i in range(len(s)):
        len1 = expand_arount_center(s, i, i)
        len2 = expand_arount_center(s, i, i+1)
        curr_len = max(len1, len2)
        if curr_len > max_len:
            max_len = curr_len
            start = i - (curr_len - 1) // 2
        
    return s[start: start + max_len]
   
def expand_arount_center(s: str, left: int, right: int) -> int:
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1


if __name__ == '__main__':
    s = "aa"
    print(longest_palindrome(s))